package com.shm.leetcode;
/**
 * @author: shm
 * @dateTime: 2020/12/1 12:02
 * @description: 34. 在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 *
 * 进阶：
 *
 * 你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 *
 *
 * 示例 1：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 8
 * 输出：[3,4]
 * 示例 2：
 *
 * 输入：nums = [5,7,7,8,8,10], target = 6
 * 输出：[-1,-1]
 * 示例 3：
 *
 * 输入：nums = [], target = 0
 * 输出：[-1,-1]
 *
 *
 * 提示：
 *
 * 0 <= nums.length <= 105
 * -109 <= nums[i] <= 109
 * nums 是一个非递减数组
 * -109 <= target <= 109
 */
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] ans = new int[]{-1, -1};
        if (nums.length <= 0) {
            return ans;
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                ans[0] = i;
                int j = ans[0];
                while (j < nums.length && nums[j] == target) {
                    j++;
                }
                ans[1] = j - 1;
                break;
            }
        }
        return ans;
    }

    /**
     * 方法一：二分查找
     * 直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见 \textit{target}target 的下标，但这个方法的时间复杂度为 O(n)O(n)，没有利用到数组升序排列的条件。
     *
     * 由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。
     *
     * 考虑 \textit{target}target 开始和结束位置，其实我们要找的就是数组中「第一个等于 \textit{target}target 的位置」（记为 \textit{leftIdx}leftIdx）和「第一个大于 \textit{target}target 的位置减一」（记为 \textit{rightIdx}rightIdx）。
     *
     * 二分查找中，寻找 \textit{leftIdx}leftIdx 即为在数组中寻找第一个大于等于 \textit{target}target 的下标，寻找 \textit{rightIdx}rightIdx 即为在数组中寻找第一个大于 \textit{target}target 的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义 binarySearch(nums, target, lower) 表示在 \textit{nums}nums 数组中二分查找 \textit{target}target 的位置，如果 \textit{lower}lower 为 \rm truetrue，则查找第一个大于等于 \textit{target}target 的下标，否则查找第一个大于 \textit{target}target 的下标。
     *
     * 最后，因为 \textit{target}target 可能不存在数组中，因此我们需要重新校验我们得到的两个下标 \textit{leftIdx}leftIdx 和 \textit{rightIdx}rightIdx，看是否符合条件，如果符合条件就返回 [\textit{leftIdx},\textit{rightIdx}][leftIdx,rightIdx]，不符合就返回 [-1,-1][−1,−1]。
     *
     * 复杂度分析
     * 时间复杂度： O(\log n)O(logn) ，其中 nn 为数组的长度。二分查找的时间复杂度为 O(\log n)O(logn)，一共会执行两次，因此总时间复杂度为 O(\log n)O(logn)。
     * 空间复杂度：O(1)O(1) 。只需要常数空间存放若干变量。
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/zai-pai-xu-shu-zu-zhong-cha-zhao-yuan-su-de-di-3-4/
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange_2(int[] nums, int target) {
        int start = binSearch(nums,target,true);
        int end = binSearch(nums,target,false)-1;
        if (start<=end&&end<nums.length&&nums[start]==target&&nums[end]==target){
            return new int[]{start,end};
        }
        return new int[]{-1,-1};
    }

    public int binSearch(int[] nums,int target,boolean lower){
        int left = 0;
        int right = nums.length-1;
        int ans = nums.length;
        while (left<=right){
            int mid = (right-left)/2+left;
            if (nums[mid]>target||(lower&&nums[mid]>=target)){
                right=mid-1;
                ans=mid;
            }else {
                left=mid+1;
            }
        }
        return ans;
    }

    public int[] searchRange_3(int[] nums, int target) {
        int[] ans = {-1,-1};

        int i=0,j=nums.length-1;
        while(i<=j){
            int mid = (j-i)/2+i;
            if(nums[mid]==target){
                int first = mid;
                int last = mid;
                while(first>=0&&nums[first]==target){
                    first--;
                }
                while(last<=nums.length-1&&nums[last]==target){
                    last++;
                }
                ans[0]=++first;
                ans[1]=--last;
                return ans;
            }else if(nums[mid]<target){
                i=mid+1;
            }else{
                j=mid-1;
            }
        }

        return ans;
    }

    /**
     * 分析：这道题要求我们在一个有序的数组中找到和目标元素相等的元素的第一个位置和最后一个位置。
     *
     * 暴力解法在最坏情况下需要遍历数组一遍，时间复杂度为 O(N)O(N) ，我们就不具体介绍这种做法了。
     *
     * 比较容易想到的做法是：当我们取中间数发现它等于目标元素的时候，马上线性地向左边逐个检查，找到和目标元素相等的元素的第 1 个位置，然后再线性地向右边逐个检查，找到和目标元素相等的元素的最后一个位置。这样代码的时间复杂度就又变成线性的了。一个更好的做法是，当看到元素和目标元素相等的时候，继续二分去查找两个边界的下标。
     *
     * 首先，我们写出代码的「框架」，然后再去实现具体的「二分查找」子函数的逻辑。
     *
     * 友情提示：写模块化的代码是程序员的基本素养，写代码的时候需要保证主线逻辑清晰，增强可读性。
     *
     * 作者：liweiwei1419
     * 链接：https://leetcode-cn.com/leetbook/read/learning-algorithms-with-leetcode/xs1z3v/
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange_4(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return new int[]{-1, -1};
        }

        int firstPosition = searchFirstPosition(nums, target);
        if (firstPosition == -1) {
            return new int[]{-1, -1};
        }

        // 能走到这里，一定是数组中存在目标元素
        int lastPosition = searchLastPosition(nums, target);
        return new int[]{firstPosition, lastPosition};
    }

    private int searchLastPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] > target) {
                // mid 以及 mid 的右边一定不是目标元素最后一次出现的位置
                // 下一轮搜索的区间是 [left, mid - 1]
                right = mid - 1;
            } else {
                // 下一轮搜索的区间是 [mid, right]
                left = mid;
            }
        }
        return left;
    }

    private int searchFirstPosition(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] < target) {
                // mid 以及 mid 的左边一定不是目标元素第 1 次出现的位置
                // 下一轮搜索的区间是 [mid + 1, right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left, mid]
                right = mid;
            }
        }

        if (nums[left] == target) {
            return left;
        }
        return -1;
    }

}
